Cartographic databases are used in computer-based systems to represent geographic features on displayable maps. These geographic features may include roads, intersections, and points-of-interest, as well as other features, such as lakes, railroad tracks, buildings, airports, stadiums, parks, mountain ranges, bridges, and so on. To permit these features to be displayed, cartographic databases usually include geographic location information in a format that allows computers to display maps illustrating the size, shape, position, and character of these various geographic features on a display device.
In order to represent these continuous features on a computer, it is necessary utilize some form of discretization. Typically, the features are represented in terms of discrete data points consisting of coordinate pairs (longitude, latitude) or coordinate triples (longitude, latitude, altitude). A point feature such as a point of interest or intersection is then represented as a single data point, while other features such as roads, lake boundaries, and so on are represented as a sequence of data points. The endpoints of the geographic features are commonly referred to as nodes while data points between the nodes are referred to as shape points. Accordingly, nodes and shape points can be used to approximate the true shape of the geographic feature. The shape points and nodes are stored in what is known as a shape point database, which may be part of a larger cartographic database. With this representation scheme, the spacing between shape points is selected such that the error between the data point representation and the actual geographic feature lies within some acceptable bound. In order to achieve a high level of accuracy and detail in the data point representation, it is often necessary to store a large number of data points.
A function available with some computerized map display systems is the ability to zoom. Zooming is the process of magnifying or reducing the scale of a map displayed on the monitor to change the level of detail. Reducing the display scale in a displayed map is referred to as zooming out, while increasing the display scale is referred to as zooming in.
To permit zooming, some cartographic databases include separate collections of location data, each with a different level of detail, which can be used by the map display function. Using these different layers of cartographic data, the map display function can provide or support zooming. However, providing multiple layers of cartographic data requires additional database storage space.
In one type of display system, the different resolution layers of cartographic data are produced by using line generalization algorithms (also referred to as line simplification algorithms). Many different line generalization algorithms are currently being used in cartography, one of which is the Douglas-Peucker algorithm. Generally, line generalization refers to a process of reducing the data points representing a linear geographic feature in a map, while maintaining the overall shape and/or trend of the feature. By applying a line generalization algorithm to a cartographic database having a large number of data points representing a high level of detail, lower resolution databases can be generated. Although known line generalization algorithms are adequate for producing cartographic data collections with different levels of detail, there is an opportunity to improve upon the speed and efficiency at which the algorithms operate.
Accordingly, there is a need for a method and system for representing cartographic data that improves upon known generalization and zooming techniques and provides an ability to reduce the storage requirements of the data without sacrificing feature resolution.